package com.demo40_组合总合2;

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public static void main(String[] args) {
        int[] ints=new int[]{2,5,2,1,2};
        List<List<Integer>> lists =combinationSum2(ints, 5);

        System.out.println(lists);
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> arrayList=new ArrayList<>();
        ArrayList<Integer> path= new ArrayList<>();
        int sum=0;

        Arrays.sort(candidates);
        dfs(arrayList,path,candidates,0,target,sum);

        return arrayList;
    }

    private static void dfs(List<List<Integer>> arrayList, ArrayList<Integer> path, int[] candidates, int startIndex, int target, int sum) {
        //1.边界条件
        if (sum==target){
            ArrayList<Integer> copy = new ArrayList<>();
            for (Integer integer : path) {
                copy.add(integer);
            }
            arrayList.add(copy);
            return;
        }

        //2.横向遍历
        for (int i = startIndex; (i < candidates.length)&&(sum+candidates[i]<=target); i++) {
            //去重, 牛逼
            if (i>startIndex&&(candidates[i]==candidates[i-1])){
                continue;
            }
            //处理本次遍历
            sum+=candidates[i];
            path.add(candidates[i]);
            //3.纵向递归
            dfs(arrayList,path,candidates,i+1,target,sum);
            //4.【回溯】
            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }
}
